package leetcode21

type ListNode struct {
	Val  int
	Next *ListNode
}

// 添加头结点简化问题
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{}
	curr := head
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			curr.Next = &ListNode{
				Val:  l1.Val,
				Next: nil,
			}
			curr = curr.Next
			l1 = l1.Next
		} else {
			curr.Next = &ListNode{
				Val:  l2.Val,
				Next: nil,
			}
			curr = curr.Next
			l2 = l2.Next
		}
	}
	for l1 != nil {
		curr.Next = &ListNode{
			Val:  l1.Val,
			Next: nil,
		}
		curr = curr.Next
		l1 = l1.Next
	}

	for l2 != nil {
		curr.Next = &ListNode{
			Val:  l2.Val,
			Next: nil,
		}
		curr = curr.Next
		l2 = l2.Next
	}
	return head.Next
}
